package org.example.myleet.p611;

import java.util.Arrays;

public class Solution1 {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                int twoEdgeSum = nums[i] + nums[j];
                int thirdEdgeMaxIdx = binarySearchMaxNonBigger(nums, j + 1, twoEdgeSum);
                if (thirdEdgeMaxIdx > -1) {
                    sum += thirdEdgeMaxIdx - j;
                }
            }
        }
        return sum;
    }

    private int binarySearchMaxNonBigger(int[] nums, int from, int target) {
        int l = from, r = nums.length - 1;
        if (l >= nums.length) {
            return -1;
        }
        if (nums[l] >= target) {
            return -1;
        }
        while (r - l > 1) {
            int m = (r + l) / 2;
            if (nums[m] > target) {
                r = m;
            } else if (nums[m] < target) {
                l = m;
            } else {
                r = m;
            }
        }
        return nums[r] < target ? r : l;
    }
}
